This invention relates to switched digital communications networks and more particularly to the use of average bandwidth utilization values respecting physical and logical links between switching nodes as a criteria for finding optimal routes for calls including connected calls.
Switched digital communication networks such as Frame Relay (FR) and Asynchronous Transfer Mode (ATM) are used for high speed, broadband data transport. Fixed length ATM cells or variable length Frame Relay packets are propagated through the network infrastructure by switching elements in the network core. Various routing criteria are used for centrally provisioning communication sessions or calls across such communication networks. Some of the common routing criteria include the following: cost of the route (due to for example, carrier tariffs or transmission medium); number of hops in a route; and bandwidth load in a route. In the case of ATM Virtual Connections, whether or not Virtual Path Connection Links are used in a route can become a factor.
Once a call is connected, it will generally use the same route for the life of that call unless a physical link in that route becomes unavailable, and the call has to be re-routed as a result.
This permanence of a route for a call in a network can result in a call traversing a less than optimal route in the course of time. This can be due to one or more of the following reasons:
1) Network growth, which may result in more optimal routes being available in the network than the one initially used to connect a call;
2) Link failures, which may force a re-route of a call. If the new route of the call following a re-route is less optimal than the route used by the call initially, then that call will be, in effect, on a less optimal route following a recovery of the failed link; or
3) Maintenance on links may make them temporarily unavailable-for use by a call.
The generally accepted method to bring a call back to an optimal route has been to run another route search for the call in question. In this case, if the cost of the new route is less than the one taken previously by that call, then the portions of the route which differ in the two alternatives for the call are disconnected and re-connected in a manner which results in minimal disruption of data.
Factors such as bandwidth load in a route are not currently considered for connected calls. The reason for not considering bandwidth load as one of the selection criteria in a route search is that doing so for connected calls is complicated. The basis of this complication is the fact that the call itself modifies the definition of bandwidth-load on its current route. Any good optimal route search algorithm should consider the network in a manner as if the call in question was not connected at all, and hence not occupying any network bandwidth resources.
This invention is applicable to the management of switched digital communications networks.
It is an object of the present invention to provide a route search implementation of load balancing which takes average link load in a route into account while providing load balancing.
It is a further object of the invention to provide an implementation which can do a route search for connected calls, and still provide load balancing.
Therefore in accordance with a first aspect of the present invention there is provided in a switched digital communication network having multiple alternate paths between a source and a destination, a method of determining the optimal path from the multiple alternatives comprising: evaluating routing characteristics of each of the alternate paths; selecting the alternate representing the least cost; if several alternatives have equal least cost then select from equal least cost paths an alternative having least number of links; if several alternatives have equal least cost and number of links then select from links having equal least cost and number of links an alternative having least average bandwidth usage.
In accordance with a second aspect of the invention there is provided in a switched digital communication network having multiple alternate paths between a source and a destination, a method of selecting the optimal path for re-routing a connected call through the network comprising: determining relative routing criteria respecting each of the multiple paths, the routing criteria including cost, number of links in the path and bandwidth load; selecting a re-route path having least cost; if several of the multiple alternatives have equal least cost, selecting a re-route path having the least number of links; if several of the alternate paths have equal least cost and equal least number of links, selecting a re-route path having a lowest average bandwidth usage; if several of the multiple paths have equal least cost, number of links and average bandwidth usage select a re-route path having the largest number of links carrying the connected call.